'''
Created on May 24, 2009

@author: user
'''

import unittest
import cProfile
import pstats
from cliques.mdp.heuristicMdp import heuristicMdp
from cliques.mdp.mdpLookahead import mdpLookahead
from cliques.randomCliqueSearch import randomCliqueSearch
from cliques.algorithmRunner import algorithmRunner
from cliques.cliqueFinder import cliqueFinder
from cliques.cliqueStarSearch import cliqueStarSearch
from cliques.totalMembershipSearch import totalMembershipSearch
from cliques.knownDegreeSearch import knownDegreeSearch
from cliques.probabilisticCliqueSearch import probabilisticCliqueSearch
from cliques.mdp.mdpBasedSearch import mdpBasedSearch
from graph import graph
from cliques.potentialBasedTester import potentialBasedTester
import cliques.experiment_runner

class test_cliqueSearch(unittest.TestCase):

    def __init__(self, methodName):
        unittest.TestCase.__init__(self, methodName)
        self.profiler = cProfile.Profile()

    def setUp(self):
        self.clique_finder = cliqueFinder()
        self.nodes = 25
        self.max_edges = min(self.nodes*8,self.nodes*(self.nodes-1)/2)
        self.profiler.enable(subcalls=True, builtins=True)
        
    def tearDown(self):
        self.algorithm=None
        self.clique_finder=None
        self.profiler.dump_stats("stats_file")
        profile_stats = pstats.Stats("stats_file")
        
        profile_stats.sort_stats('time')
        profile_stats.print_stats(15)        

    def test_lookahead_mdp(self):
        self.algorithm = mdpBasedSearch(mdpLookahead,"lookahead-MDP")
        self.nodes = 10
        self.max_edges = 12#min(self.nodes*5,self.nodes*(self.nodes-1)/2)        
        self.verify_clique_search()        

    def test_heuristic_mdp(self):
        self.algorithm = mdpBasedSearch(heuristicMdp,"heuristic-MDP")
        self.nodes = 5
        self.max_edges = min(self.nodes*8,self.nodes*(self.nodes-1)/2)        
        self.verify_clique_search()        
        

    def test_mdp_clique_search(self):
        self.algorithm = mdpBasedSearch(cliques.mdp.mdpSolver.smarterCliqueMdpSolver,"smarter-MDP")
        self.nodes = 5
        self.max_edges = min(self.nodes*8,self.nodes*(self.nodes-1)/2)        
        self.verify_clique_search()

    def test_probabilistic_clique_search(self):
        self.algorithm = probabilisticCliqueSearch()
        self.nodes = 20
        self.max_edges = min(self.nodes*2,self.nodes*(self.nodes-1)/2)        
        
        self.verify_clique_search()

    def test_known_degree_search(self):
        self.algorithm = knownDegreeSearch()
        self.verify_clique_search()
    

    def test_random_clique_search(self):
        self.algorithm = randomCliqueSearch()
        self.verify_clique_search()
    
    def test_total_membership_search(self):
        self.algorithm = totalMembershipSearch()
        self.verify_clique_search()

    
    def test_potential_based_tester(self):
        self.algorithm = potentialBasedTester()
        self.verify_clique_search()    

    def test_clique_star_search(self):
        self.algorithm = cliqueStarSearch()
        self.verify_clique_search()
    
    def verify_clique_search(self):
        nodes = self.nodes
        for edges in xrange(nodes-1,self.max_edges):
            print "--- Generating graph[%d,%d] --- " % (nodes,edges)
            test_graph = graph()
            test_graph.generate(nodes,edges)
            start_node = cliques.experiment_runner.choose_start(test_graph)
            
            # Create the connected component containing the start node
            components = test_graph.connected_components()
            start_component = components[start_node]
            connected_nodes=filter(lambda x:components[x]==start_component,components.keys())
            connected_graph = graph()
            for connected_node in connected_nodes:
                connected_graph.add_node(connected_node)
            for connected_node in connected_nodes:
                for connected_neighbor in test_graph.neighbors(connected_node):
                    connected_graph.add_edge(connected_node,connected_neighbor)
            
            for k in xrange(3,min(7,nodes)):    
                
                        
                # Checking if there is a clique
                self.clique_finder.setup(connected_graph)                
                existing_clique = self.clique_finder.find_clique(k,connected_graph.nodes())
                if existing_clique is not None:
                    existing_clique = set(existing_clique)                
                
                self.algorithm.setup(test_graph, k, start_node)
                #print "- Running the algorithm..."
                #self.algorithm.status()
                while self.algorithm.halt()==False:
                    # DEBUG print "    Iteration [%d]" % self.algorithm.iteration
                    # If clique exists in the graph, 
                    # verify that hasn't been discovered yet
                    if existing_clique is not None:
                        assert len(set(self.algorithm.expanded).intersection(existing_clique))<k-1          
                    self.algorithm.step()
                    #self.algorithm.status()
                # If no clique exists - verify all nodes were expanded
                if existing_clique is None:
                    assert self.algorithm.iteration==len(connected_nodes)
                else:
                    self.clique_finder.setup(self.algorithm.ckg)                    
                    possible_k_clique = self.clique_finder.find_clique(k,self.algorithm.ckg.nodes())
                    assert possible_k_clique is not None
                    assert len(existing_clique)==k
                    assert len(possible_k_clique)==k               


    def test_clique_not_in_pcdb(self):
        # Read graph
        graph_file_name = "clique_not_in_pcdb.graph"
        graph_file = open(graph_file_name,"r+")
        read_xml = graph_file.read()
        graph_file.close()
        a_graph = graph()
        a_graph.read(read_xml)
        k=3
        start_node = u'65'
        algo = potentialBasedTester()
        algo.setup(a_graph, k, start_node)
            
        runner = algorithmRunner()
        runner.run(algo)
        
    def test_fast_clique_160(self):
        graph_file_name = "fast_clique_160.graph"
        graph_file = open(graph_file_name,"r+")
        read_xml = graph_file.read()
        graph_file.close()
        a_graph = graph()
        a_graph.read(read_xml)
        k=3
        start_node = u'160'
        algo = cliqueStarSearch()
        algo.setup(a_graph, k, start_node)
            
        runner = algorithmRunner()
        runner.run(algo)
        
        algo.statistics()
        

if __name__ == "__main__":
    #import sys;sys.argv = ['', 'test_cliqueSearch.test_lookahead_mdp']
    unittest.main()
    
    
   
    
    
    